In this paper we consider discrete robot path planning problems on metricgraphs. We propose a clustering method, Gamma-Clustering for the planning graphthat significantly reduces the number of feasible solutions, yet retains asolution within a constant factor of the optimal. By increasing the inputparameter Gamma, the constant factor can be decreased, but with less reductionin the search space. We provide a simple polynomial- time algorithm for findingoptimal Gamma-Clusters, and show that for a given Gamma, this optimal isunique. We demonstrate the effectiveness of the clustering method on travelingsalesman instances, showing that for many instances we obtain significantreductions in computation time with little to no reduction in solution quality.
展开▼
